package com.mdnote.jianzhi_offer.search;

/**
 * @author Rhythm-2019
 * @version 1.0
 * @date 2020/10/12
 * @description 剑指 Offer 11. 旋转数组的最小数字
 */
public class Offer11 {


    public static void main(String[] args) {
        Offer11 offer11 = new Offer11();
        int i = offer11.minArray(new int[]{4, 9, 4, 5, 6});
        System.out.println(i);
    }
    public int minArray(int[] numbers) {

        // Binary Search
        if (numbers[0] < numbers[numbers.length - 1]) {
            return numbers[0];
        }
        return binary_search(numbers);
    }

    private int binary_search(int[] numbers) {

        int left = 0, right = numbers.length - 1;
        int minVal = left;
        while (left <= right) {

            if (right - left == 1) {
                minVal = right;
                break;
            }
            int mid = left + ((right - left) >> 1);

            if (numbers[left] == numbers[right] && numbers[mid] == numbers[left]) {
                minVal = linear_search(numbers, left, right);
                break;
            } else {
                if (numbers[left] > numbers[mid]) {
                    // the min value in left
                    right = mid;
                } else if (numbers[right] <= numbers[mid]) {
                    // the min value in right
                    left = mid;
                }

            }
        }
        return numbers[minVal];
    }

    public int linear_search(int[] numbers, int left, int right) {
        int pre = numbers[0];
        for (int i = 1; i < numbers.length; i++) {
            if (pre > numbers[i]) {
                return i;
            }
            pre = numbers[i];
        }
        return 0;
    }
}
